package com.icesoft.core.common.helper.tree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public abstract class TreeUtils {

	public static <T extends BaseTree<T>> List<T> hierarchy(Collection<T> list) {
		return hierarchy(list, null);
	}

	public static <T extends BaseTree<T>> T hierarchy(T top, Collection<T> list) {
		return hierarchy(top, list, null);
	}

	public static <T extends BaseTree<T>> void hierarchy(Queue<T> topNodes, Collection<T> subs) {
		hierarchy(topNodes, subs, null);
	}

	public static <T extends BaseTree<T>> List<T> hierarchy(Collection<T> list, TreeConsumer<T> biConsumer) {
		Queue<T> queue = new LinkedList<>();
		List<T> subs = findSubs(list);
		list.removeAll(subs);
		queue.addAll(list);
		hierarchy(queue, subs, biConsumer);
		return new ArrayList<>(list);
	}

	public static <T extends BaseTree<T>> T hierarchy(T top, Collection<T> list, TreeConsumer<T> biConsumer) {
		Queue<T> queue = new LinkedList<>();
		queue.offer(top);
		hierarchy(queue, list, biConsumer);
		return top;
	}

	public static <T extends BaseTree<T>> void hierarchy(Queue<T> topNodes, Collection<T> list,
			TreeConsumer<T> biConsumer) {
		int levelCount = topNodes.size();
		int nextLevelCount = 0;
		int level = 1;
		while (!topNodes.isEmpty()) {
			T parent = topNodes.poll();
			if (biConsumer != null) {
				biConsumer.forEach(parent, level);
			}
			for (T baseTree : list) {
				if (baseTree.isParent(parent)) {
					topNodes.offer(baseTree);
					nextLevelCount++;
					if (parent.getChildren() == null) {
						parent.setChildren(new ArrayList<>());
					}
					parent.getChildren().add(baseTree);
				}
			}
			if (parent.getChildren() != null) {
				list.removeAll(parent.getChildren());
			}
			levelCount--;
			if (levelCount == 0) {
				level++;
				levelCount = nextLevelCount;
			}
		}
	}

	public static <T extends BaseTree<T>> void forEach(T top, TreeConsumer<T> biConsumer) {
		Queue<T> queue = new LinkedList<>();
		queue.add(top);
		int levelCount = 1;
		int nextLevelCount = 0;
		int level = 1;
		while (!queue.isEmpty()) {
			T parent = queue.poll();
			if (biConsumer != null) {
				biConsumer.forEach(parent, level);
			}
			if (parent.getChildren() != null) {
				queue.addAll(parent.getChildren());
				nextLevelCount = parent.getChildren().size();
			}
			levelCount--;
			if (levelCount == 0) {
				level++;
				levelCount = nextLevelCount;
			}
		}
	}

	private static <T extends BaseTree<T>> List<T> findSubs(Collection<T> list) {
		List<T> subs = new ArrayList<>();
		for (T sub : list) {
			for (T t : list) {
				if (sub.isParent(t)) {
					subs.add(sub);
					break;
				}
			}
		}
		return subs;
	}
}
